#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#include <immintrin.h>
//#include <emmintrin.h>
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define fi first
#define se second
#define pii pair<int,int>
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
const int N=1e5+5,base=999983,Mod=998244353;
//char buf[(1<<21)+5],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void chmx(int &x,int y){(x<y)&&(x=y);}
inline void chmn(int &x,int y){(x>y)&&(x=y);}
inline void Add(int &x,int y){(x=x+y+Mod)%=Mod;}
inline int read(){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f?-x:x;
}
void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n%10+'0');
}
int n,k;
int a[N];
vector<int>q[N];
vector<pii>s[5];
int tot[5];
long long ans; 
pii tr[N<<2];
int lz[N<<2]; 
inline void down(int x,int k){tr[x].fi+=k;lz[x]+=k;}
inline pii pushup(pii lc,pii rc){
	pii res={0,0};
	res.fi=min(lc.fi,rc.fi); 
	if(lc.fi<=rc.fi) res.se+=lc.se;
	if(lc.fi>=rc.fi) res.se+=rc.se;
	return res;
}inline void pushdown(int x){
	if(lz[x]) down(ls(x),lz[x]),down(rs(x),lz[x]),lz[x]=0;
}void build(int x,int l,int r){
	if(l==r){tr[x]={0,1};return;}
	int mid=(l+r)>>1;
	build(ls(x),l,mid);build(rs(x),mid+1,r);
	tr[x]=pushup(tr[ls(x)],tr[rs(x)]);
}
void updata(int x,int l,int r,int L,int R,int k){
	if(L>R) return; 
	if(L<=l&&r<=R){
		down(x,k);
		return;
	}int mid=(l+r)>>1;pushdown(x);
	if(L<=mid)updata(ls(x),l,mid,L,R,k);
	if(R>mid) updata(rs(x),mid+1,r,L,R,k); 
	tr[x]=pushup(tr[ls(x)],tr[rs(x)]);
}pii qry(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R) return tr[x];
	int mid=(l+r)>>1;pii res={1e16,0};pushdown(x);
	if(L<=mid)res=pushup(res,qry(ls(x),l,mid,L,R));
	if(R>mid)res=pushup(res,qry(rs(x),mid+1,r,L,R));
	return res;
}
signed main(){
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(0); cout.tie(0);
	n=read(),k=read();int mx=0;
	
	For(i,1,n){
		a[i]=read();
		mx=max(mx,a[i]);
	}
	For(i,1,n)For(j,1,k+1) q[i].push_back(n+1);
	if(n*mx<=1000000)
	Rof(i,n,1){
		q[a[i]].push_back(i);
		For(j,1,k) s[j].clear(),tot[j]=0;
//		puts("");
		For(j,1,mx){
			For(t,0,k-1){
				s[t+1].push_back({q[j][q[j].size()-1-t],q[j][q[j].size()-1-t-1]-1});
//				cout<<t+1<<":"<<q[j][t]<<" "<<q[j][t+1]-1<<endl;
				
			}
		}
		For(t,1,k){
			sort(s[t].begin(),s[t].end());
			For(j,1,s[t].size()-1){
				s[t][j].fi=max(s[t][j].fi,s[t][j-1].se+1);
				
			}
		}
		while(1){
			bool flag=1;
			For(t,1,k){
				if(tot[t]==s[t].size()) flag=0;
			}if(!flag) break;
			
			int p=0,mx=0;
			For(t,1,k)if(s[t][tot[t]].se>mx)p=t,mx=s[t][tot[t]].se;
			int L=s[p][tot[p]].fi,R=s[p][tot[p]].se;
			For(t,1,k){
				L=max(s[t][tot[t]].fi,L);
				R=min(s[t][tot[t]].se,R);
			}
			if(L<=R)ans+=R-L+1;
			For(t,1,k)if(s[t][tot[t]].se==R) tot[t]++;
		}
	}else{build(1,1,n);
		Rof(i,n,1){
			updata(1,1,n,q[a[i]][q[a[i]].size()-1],q[a[i]][q[a[i]].size()-2]-1,-1);
			q[a[i]].push_back(i);
			updata(1,1,n,i,q[a[i]][q[a[i]].size()-2]-1,1);
			pii qr=qry(1,1,n,i,n);
			ans+=n-i+1-qr.se*(!qr.fi);
		} 
	}
	printf("%lld\n",ans);
#ifdef LOCAL
    Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}

